package problems.solved;

import java.util.HashMap;
import java.util.Map;

public class Problem14 {
	private static final long TARGET = 1000000;

	private static final int CACHE_SIZE = (int) (2*TARGET); //apparently, bigger is better.
	private static Map<Long, Integer> cache = new HashMap<Long, Integer>(CACHE_SIZE);

	public static void main(String... args) {
		long number = 0;
		int maxSize = 0;
		
		for (long i = 1; i <= TARGET; i++) {
			int size = size(i);
			if (size > maxSize) {
				maxSize = size;
				number = i;
			}
		}
		
		System.out.printf("longest: %d (%d)%n", number, maxSize); //837799
	}
	
	private static int size(long i) {
		if (i == 1L) {
			return 1;
		}
		if (cache.containsKey(i)) {
			return cache.get(i);
		}
		final int size = size(process(i)) + 1;
		if (i < CACHE_SIZE) {
			cache.put(i, size);
		}
		return size;
	}

	private static long process(long n) {
		return n % 2 == 0 ? n/2 : 3*n + 1;
	}
}
